package org.bear.array;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/*
    560.和为K的子数组

    输入：nums = [1,2,3], k = 3
    输出：2
       0 a b c d e
       sum(c) - sum(b) = k
 */
public class SubarraySum {

    public int subarraySum(int[] nums, int k) {
        int[] sums = new int[nums.length+1];
        sums[0] = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);
        for(int i=0;i<nums.length;i++){
            sums[i+1] = sums[i] + nums[i];
        }
        int res = 0;
        for(int i=1;i<nums.length+1;i++){
            int needValue = sums[i] - k;
            res += map.getOrDefault(needValue, 0);
            if (map.get(sums[i])==null){
                map.put(sums[i], 1);
            }else  {
                map.put(sums[i], map.get(sums[i])+1);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        SubarraySum s = new SubarraySum();
        System.out.println(s.subarraySum(new int[]{1,2,3}, 3));
    }

}
